I. Field Of The Invention
The present invention relates generally to queues. More particularly, the present invention relates to measuring the length or available occupancy (status) of queues and a switch system for utilizing the status.
II. Description of the Related Art
As the use of computers increases in businesses, they must be networked in order to make them a productive work tool. Without networks, copying large files from one workstation to another would require copying the files to portable disks that are carried to the next work station to be loaded. This is not feasible for very large files in the megabytes or gigabytes range since that would require a large number of disks and considerable time to copy from one workstation to another.
As computer technology evolves, computers are operating at greater speeds. It's not unusual to find 125 MHz central processing units (CPU) on desktops and in homes. This presents a problem when the computers are networked since the network must be able to transfer data in large volumes and at high rates so that they do not become a data bottleneck, causing the computer to slow down to keep pace with the network.
One such high speed network standard is the Ethernet network. This network couples computers at high data rates to allow efficient data transfer. Switches on the network typically have data cell queues that hold data to be transferred to other computers. These queues store cells temporarily while waiting to be transmitted to another address.
In order to facilitate the operation of the switch, accurate information regarding the queues is needed. Classical methods are using a queue threshold mechanism which is comparing the queue fullness with a pre-assigned queue threshold. Various proprietary schemes are implemented in particular switch designs.
Queues, since they are some form of memory, have a finite length. Therefore, if too many cells are stored in the queue, it can become full. This means the incoming cells either overwrite the stored cells or they are simply discarded until the queue has room. There is a resulting need for a method and apparatus to measure the occupancy status of a queue and communicate this status to the relevant portions of the network switch.
Existing techniques for addressing the problem of the queue becoming full and resulting in loss of data, either within the queue (for overwrite) or of incoming data (by rejection of incoming data). Typically, a back pressure throttle control mechanism provides a high-water mark threshold is chosen within the fixed size queue. When the queue fills beyond the high water mark, a signal is output to the input processing device which is providing the inputs to the queue, to throttle back (either totally stop or decrease the speed by a present amount of) incoming cells to the queue. This method has a number of limitations. First, the decision is made within the queue, based on an absolute threshold level being exceeded. There is no raw information or flow rate or history provided to other processing elements such as input and output elements in a switch, or call admission control processing element, to permit the processing unit to decide how to regulate cell input and/or output to the queue. Furthermore, the high water mark back pressure throttle control provides information of when to decrease or throttle the incoming cells, but does not provide information on how much to decrease or when to increase cell flow.